              IOI. 3 (Programare). Pe un interval de timp [0,Endtime] dat,
trebuie asigurata paza unei galerii de arta de catre N paznici, fiecare paznic
i (1iN) fiind programat pentru un interval [T1(i),T2(i)] dat. Prin schema de
garda ntelegem ansamblul format din vectorii T1 si T2. Timpul este dat n
minute. Se cere:
   1. Sa se verifice daca exista cel putin doi paznici n orice moment de timp
din intervalul considerat. In caz negativ:
   2. Sa se determine toate perioadele pentru care conditia de mai sus nu este
ndeplinita;
   3. Fiind dat numarul natural Length, sa se determine numarul minim de
paznici suplimentari angajati pentru cte Length minute, necesari pentru a
satisface conditia ceruta;
   4. Sa se determine daca schema de garda initiala poate fi modificata pentru
a satisface conditia data, permitndu-se schimbarea nceputului de garda a
paznicilor, dar nu si a lunginii acestei perioade; n caz afrmativ, se cere sa
se listeze o noua schema de garda, care n plus sa fie obtinuta din cea
initiala cu un numar minim de modificari.
=========================================================
Solutia 1 (Miahi Stroe):
    Schema de garda este simulata intr-un vector A, unde A[i] indica numarul
  de paznici activi la minutul i dupa inceput.
    Vectorul se completeaza astfel: pentru fiecare paznic i, valorile dintre
  T1(i) si T2(i) cresc cu o unitate. Daca vectorul are componente cu valori
  mai mici decit 2, se afiseaza intervalele cu aceste componente.
    Punctul 3 se rezolva destul de simplu: se gaseste primul moment i cu mai
  putin de 2 paznici si se planifica un paznic care este activ LENGTH minute
  incepind cu minutul i. Se repeta subrutina de mai sus pina cind schema
  indeplineste conditia 1.
    Punctul 4 se rezolva prin determinarea celui mai mic numar mai mare sau
  egal cu Endtime care se poate obtine printr-o suma a perioadelor pe care
  sunt angajati o parte din cei n paznici. Daca diferenta dintre suma tuturor
  perioadelor si numarul gasit este mai mare sau egala cu Endtime, schema se
  poate modifica. Numarul respectiv este gasit prin programare dinamica; de
  fapt, se gasesc toate sumele posibile obtinute cu perioade ale paznicilor.
    Ideea programarii dinamice este urmatoarea: la pasul i (1<=i<=n) se
  afla sumele posibile cu perioadele primilor i paznici.
       Exemplu:
       - perioade: 2 3 6 4
       i=1    2                               \
       i=2    2 3 5                             > sumele de la pasul i
       i=3    2 3 5 6 8 9 11                  /
       i=4    2 3 4 5 6 7 8 9 10 11 13 15

    Noua schema de garda se genereaza usor daca nu este nevoie sa fie optima,
  in caz contrar folosindu-se metoda backtracking. Generarea unei scheme
  neoptime foloseste rezultatele partiale obtinute prin aplicarea programarii
  dinamice. Nu am implementat gasirea schemei optime, deoarece nu este clar
  daca numar minim de modificari inseamna 0 sau 1 pentru fiecare paznic sau
  intervalul de translatie pentru fiecare paznic.

var fi,fo:text;
    luati,t1,t2,lung:array[1..100]of word;
    a:array[0..60000]of byte;
    nr,total,length,i,j,k,l,m,n,endtime:longint;
    s:string;

procedure readdata;
begin
  write('Type input file name ');
  readln(s);
  assign(fi,s);
  write('Type output file name ');
  readln(s);
  assign(fo,s);
  reset(fi);
  rewrite(fo);
  readln(fi,endtime);
  readln(fi,n);
  for i:=1 to n do
      read(fi,t1[i]);
  readln(fi);
  for i:=1 to n do
      read(fi,t2[i]);
  readln(fi);
  close(fi);
end;

procedure solve12;
begin
  for i:=1 to n do
      for j:=t1[i] to t2[i] do
          inc(a[j]);
  k:=1;
  for i:=1 to endtime do
      if a[i]<2 then
         begin
           if k=1 then writeln(fo,'The guards'' schedule is bad ');
           k:=0;
           write(fo,i,' ');
           while (a[i]<2) and(i<=endtime) do inc(i);
           writeln(fo,i-1);
           if i>endtime then i:=endtime;
         end;
  if k=1 then
     begin
       writeln(fo,'There are at least two guards every moment');
       close(fo);
       halt;
     end
end;

procedure solve3;
begin
  write('Input LENGTH ');
  readln(length);
  i:=1;
  while i<=endtime do
    begin
      while(a[i]>1)and(i<=endtime+1) do inc(i);
      if i=endtime+1 then
         begin
           writeln(fo,nr,' new guards will be hired');
           exit;
         end
         else
         begin
           inc(nr);
           for j:=1 to length do
               inc(a[j-1+i]);
         end;
    end;
  writeln(fo,nr,' new guards will be hired');
end;

procedure solve4;
procedure rec(i:word);
var j:word;
begin
  if i=0 then exit;
  rec(i-lung[a[i]]);
  if i-1>endtime then j:=endtime+1 else j:=i;
  writeln(fo,j-lung[a[i]],' ',j-1);
  luati[a[i]]:=1;
end;

begin
  for i:=1 to n do
      begin
        lung[i]:=t2[i]-t1[i]+1;
        total:=total+lung[i];
      end;
  if total<2*endtime then
     begin
       writeln(fo,'A new schedule could not be created ');
       exit;
     end;
  fillchar(a,sizeof(a),0);
  a[0]:=255;
  for i:=1 to n do
      for j:=lung[i] to 60001 do
          if (a[j]=0)and(((a[j-lung[i]]<>0)and(a[j-lung[i]]<i))or(j=lung[i]))then a[j]:=i;

  i:=endtime+1;
  while a[i]=0 do inc(i);
  if total-i<endtime then
     begin
       writeln(fo,'A new schedule could not be created ');
       exit;
     end;
  writeln(fo,'A new schedule can be created');

  writeln(fo,'This is a schedule (probably not the optimal one) :');
  rec(i);
  nr:=0;
  for i:=1 to n do
      if luati[i]=0 then
         begin
           writeln(fo,nr,' ',nr+lung[i]-1);
           nr:=nr+lung[i]+1;
           if nr+lung[i+1]>endtime then nr:=endtime-lung[i+1]+1;
         end;

end;

begin
  readdata;
  solve12;
  solve3;
  solve4;
  close(fo);
end.
--------------------------------------------
Solutia mea:
Algoritm:
              Se poate folosi un vector PROGRAM(0..Endtime) iniializat cu zero.
In prima faz[ se aplic[ urm[torii pai;
Pentru fiecare i:=1,N
   Pentru fiecare j:=T1(i),T2(i)
      PROGRAM(j):=PROGRAM(j)+1.
Acum:
Pentru punctul 1: totul se reduce la a verifica condiia:
                                              PROGRAM(i)2 zi,0iEndtime
2) Se determin[ secvenele compacte din vectorul PROGRAM care au toate elementele 0 sau 1;
3) Se introduce un vector SUPL(0..Endtime) care are c1 pe o poriune de lungime Lenght
ncepnd cu poziia primului element strict mai mic dect 2 din PROGRAM, 0 n rest.
Se face PROGRAM:=PROGRAM+SUPL (component[ cu component[);
Dac[ noul vector PROGRAM mai are elemente <2, algoritmul (relativ la acest punct) se reia.
In final, num[rul de paznici suplimentari este egal cu num[rul de relu[ri ale algoritmului. 
4) Se folosete vectorul PROGRAM obinut la pasul 1.
Dac[ 0iEndtimePROGRAM(i)/(Endtime+1)<2, r[spunsul este negativ (sunt necesari paznici
suplimentari). Altfel:
-               Se alege un paznic p prin scoaterea c[ruia vectorul PROGRAM are cele mai puine elemente
>2; se lucreaz[ cu noul vector PROGRAM. 
-               Se construiete un vector SUPL(0,Endtime) cu 1 pe T2(p)-T1(p) poziii  0 n rest,
astfel nct s[ se meximizeze num[rul de elemente 2 din vectorul PROGRAM:=PROGRAM+SUPL.
Se modific[ corespunz[tor elementele T1(p),T2(p).
              Procedeul se reia pn[ cnd PROGRAM(i)2 zi,0iEndtime.
               Program:
type leg=^pereche;
     pereche=record
             p1,p2:integer;
             end;
     pauz=record
          inceput,sfarsit:integer;
          end;
var EndTime,Lngth,N,i,durata:integer;
    T1,T2:array[1..100] of integer;
    pauza:pauz;
--------------------------------------------------
function sunt_paznici(timp:integer):leg;
{ intoarce 2 paznici daca exista cel putin 2 paznici la momentul timp.
           Daca nu, intoarce 0 }
var result:leg;
    i:integer;
begin
result^.p1:=0;
result^.p2:=0;
i:=1;
while (i<=N) and (result^.p2=0) do
      begin
      if (T1[i]<=timp) and (T2[i]>=timp) then
         if result^.p1<>0 then result^.p2:=i
                          else result^.p1:=i;
      i:=i+1;
      end;
sunt_paznici:=result;
end;
--------------------------------------------------
begin
readln(EndTime,N);
for i:=1 to n do readln(t1[i],t2[i]);
durata:=0;
pauza.inceput:=0;
pauza.sfarsit:=0;
for i:=1 to EndTime do
    if sunt_paznici(i)^.p2=0 then
       begin
       if durata=0 then writeln('Nu exista cel putin 2 paznici in
fiecare moment.');
       if pauza.inceput=0 then pauza.inceput:=i;
       durata:=durata+1;
       end
    else if pauza.inceput<>0 then
            begin
            pauza.sfarsit:=i-1;
           writeln('(',pauza.inceput:3,',', pauza.sfarsit:3,')');
            pauza.inceput:=0;
            pauza.sfarsit:=0;
            end;
if pauza.inceput<>0 then
   begin
   pauza.sfarsit:=i;
  writeln('(',pauza.inceput:3,',', pauza.sfarsit:3,')');
   pauza.inceput:=0;
   pauza.sfarsit:=0;
   end;
if durata=0 then writeln('Exista cel putin 2 paznici in fiecare
moment.')
else begin
     readln(Lngth);
     writeln('Mai sunt necesari ',trunc(durata/Lngth)+1:3,' paznici.');
     end;
end.
-------------------------------------------
